package org.sg20.parsename;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

public class ACAutomaton {
    private final ACNode root;

    public ACAutomaton() {
        root = new ACNode("", (char) 0, null, false);
        root.fail = root;
    }

    public boolean insertWord(String s) {
        boolean contain = true;

        ACNode cur = root;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (cur.insertChild(c, i == s.length() - 1))
                contain = false;
            cur = cur.getChild(c);
        }
        //if the trie tree contains the word, return false!!!
        return !contain;
    }

    public void buildGraph() {
        Queue<ACNode> q = new LinkedList<>();

        for(ACNode child : root.children.values()){
            child.fail = root;
            q.offer(child);
        }
        while (q.size() > 0) {
            ACNode cur = q.poll();
            for (ACNode child : cur.children.values()) {
                if (cur.fail.children.containsKey(child.ch)) {
                    child.fail = cur.fail.children.get(child.ch);
                } else {
                    ACNode failn = cur.fail;
                    while (!failn.children.containsKey(child.ch) //loop
                            && !failn.isRoot()) {// not root
                        failn = failn.fail;
                    }
                    if(failn.children.containsKey(child.ch)) {
                        child.fail = failn.children.get(child.ch);
                    }else
                        child.fail = failn;
                }
                //add the child to the queue
                q.offer(child);
            }
        }
    }

    public String parseString(String s) {
        StringBuilder str = new StringBuilder();
        ACNode cur = root;
        for (int i = 0; i < s.length(); i++) {
            //System.out.println("aaa");
            cur = cur.getTransByChar(s.charAt(i));
            //System.out.println("kkk");
            if (cur.isEnd()) {
                //System.out.println(cur.getPrefix());
                str.append(cur.getPrefix());
                str.append("\t");
                cur = root;
            }
        }
        //System.out.println("aaaaaaaaa");
        return str.toString();
    }

    public static class ACNode {
        private final String prefix;
        private final char ch;

        private final ACNode father;
        private final HashMap<Character, ACNode> children;
        private ACNode fail;
        private boolean isend;

        public ACNode(String pref, char c, ACNode fath, boolean ise) {
            prefix = pref;
            ch = c;
            father = fath;
            children = new HashMap<>();
            isend = ise;
            fail = null;
        }

        public ACNode getTransByChar(char c) {
            if (!children.containsKey(c)) {

                ACNode cur = this;

                while (!cur.children.containsKey(c) && !cur.isRoot()) {
                    // dead loop
                    cur = cur.fail;
                }

                if (cur.children.containsKey(c)) {//root
                    return cur.children.get(c);
                }
                //root and no trans
                return cur;
            }
            return children.get(c);
        }


        public void setEnd() {
            isend = true;
        }

        public boolean isEnd() {
            return isend;
        }

        public boolean isRoot() {
            return father == null;
        }

        public String getPrefix() {
            return prefix;
        }


        public boolean insertChild(char c, boolean ise) {
            // child is not END but the node to be inserted is END, we will change the mode.
            if (children.containsKey(c) && !(!children.get(c).isEnd() && ise))
                return false;

            if (!children.containsKey(c)) {
                children.put(c, new ACNode(prefix + c, c, this, ise));
            } else if (ise) //child is END but the node to be inserted is not END
                children.get(c).setEnd();
            return true;
        }

        public ACNode getChild(char c) {
            if (!children.containsKey(c))
                return null;
            return children.get(c);
        }
    }

}
